package org.example.myleet.p1713;

import java.util.*;

/**
 * 哈希表 + 最长增长子序列（二分法）
 * 思路：
 * 先通过读题，将题目的意思转化为，在arr中找出最长的target的子序列，然后target的长度减去最长子序列的长度就是需要操作的次数
 * 因为target的子序列是target中的元素保持相对位置形成的，且target中的元素是彼此不同的
 * 因此将target中的元素的位置信息标记到arr中，在arr中，找到target元素位置标记保持增长的最长长度，就是target的元素在arr中最长的子序列长度
 * 也就是转化为最长增长子序列问题（LIS，Longest Increasing Subsequence）
 * 最长增长子序列长度可以通过单调递增栈（二分法）找到
 * 最长上升子序列相关：https://blog.csdn.net/lxt_Lucia/article/details/81206439
 */
public class Solution {
    public int minOperations(int[] target, int[] arr) {
        //先用哈希表找到target中所有元素的下标，即元素的相对顺序，将arr转成用target元素下标做的掩码列表
        Map<Integer, Integer> targetIdxMap = new HashMap<>();
        for (int i = 0; i < target.length; ++i) {
            targetIdxMap.put(target[i], i);
        }
        for (int i = 0; i < arr.length; ++i) {
            Integer idx = targetIdxMap.getOrDefault(arr[i], null);
            if (null == idx) {
                //找不到的给-1
                arr[i] = -1;
            } else {
                arr[i] = idx;
            }
        }
        //单调上升栈的长度
        int maxIncreasingLen = 0;
        //单调上升栈
        int[] stack = new int[arr.length];
        for (int idxMask : arr) {
            if (idxMask == -1) {
                continue;
            }
            //找到栈顶元素
            Integer top = null;
            if (maxIncreasingLen > 0) {
                top = stack[maxIncreasingLen - 1];
            }
            if (top != null && top >= idxMask) {
                //如果栈顶元素大于arr中的掩码值，则利用二分法找到第一个比掩码值大的数，然后用掩码值替换
                //思路是贪心，解释就是如果遇到更小的掩码，则这个掩码在后面的探索过程中肯定更可能容纳更多上升掩码的加入
                //所以要在不改变栈的长度的情况下减小单调上升栈中的元素的值
                int l = 0, r = maxIncreasingLen - 1;
                while (r - l > 1) {
                    int mid = (r + l) / 2;
                    int m = stack[mid];
                    if (m > idxMask) {
                        r = mid;
                    } else {
                        l = mid;
                    }
                }
                int replaceIdx = stack[l] < idxMask ? r : l;
                stack[replaceIdx] = idxMask;
            } else {
                stack[maxIncreasingLen++] = idxMask;
            }
        }
        //需要操作的次数就是target的长度减去最长上升子序列的长度
        return target.length - maxIncreasingLen;
    }
}
